Breadth-First Search explores a graph in expanding layers, like ripples in a pond.

  • BFS explores in layers (or levels) starting from a source node s.
  • It first visits s (level 0), then all of its direct neighbors (level 1), then their neighbors (level 2), and so on.
  • This systematic, layer-by-layer process is managed with a FIFO queue.
  • Because it expands outward one level at a time, BFS is guaranteed to find the shortest path from s to any other node in an unweighted graph.
  • The core takeaway is that BFS discovers vertices in order of non-decreasing distance from the source.
Formal Definition: Level

For a given start vertex s, the level of a vertex v, denoted level[v], is the minimum number of edges on any path from s to v.